#include "linearList.h"
using namespace std;
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

//初始化顺序表
sequenceList::sequenceList(const int& cap, const int& initLen, float initArr[])
{
    maxCapcity = cap;//顺序表容量
    curNumberOfItem = initLen;//初始化数组长度
    myList = new float[maxCapcity];
    for (int i = 0; i < initLen; ++i) myList[i] = initArr[i];//初始化数组
}

//销毁顺序表
sequenceList::~sequenceList()
{
    delete[] myList;
}

//添加元素
bool sequenceList::addItem(const float& num)
{
    if (curNumberOfItem >= maxCapcity) return false;//添加失败返回false
    myList[curNumberOfItem++]=num;//添加元素
    return true;
}

//插入元素
bool sequenceList::insertItem(const int& index, const float& num)
{
    if (index < 0 || index >curNumberOfItem)
        return false;//舍去不符合题意的index值
    for (int i = curNumberOfItem; i > index; --i) myList[i] = myList[i - 1];//index位置后面的元素后移
    myList[index] = num;//插入元素
    ++curNumberOfItem;
    return true;
}

//删除元素
int sequenceList::deleteItem(const float& item)
{
    int pos = -1;  // 记录第一个匹配项的下标
    // 找到第一个匹配项
    for (int i = 0; i < curNumberOfItem; ++i) {
        if (myList[i] == item) {
            pos = i;
            break;
        }
    }
    // 如果找到了，就将其删除（后面元素前移一位）
    if (pos != -1) {
        for (int i = pos; i < curNumberOfItem - 1; ++i) {
            myList[i] = myList[i + 1];
        }
        --curNumberOfItem;
    }
    return pos;  // 返回删除位置，找不到返回 -1
}

//查找元素（按序号找）
 bool sequenceList::locate(const int& index, float& val)
 {
    //舍去不合理的value值
    if (index < 0 || index >= curNumberOfItem)   // 只要越界就不动 val
        return false;
    val = myList[index];
    return true;
 }

//查找元素（按值查找）
 int sequenceList::locate(const float& num)
 {
    for(int i=0;i<curNumberOfItem;i++)
    {
        if(myList[i]==num) return i;//找到这个值，并返回它所在的位置
    }
    return -1;
 }

//倒序排列元素(使用原空间)
void sequenceList::reverse()
{
    int i = 0, j = curNumberOfItem - 1;
    while (i < j) {//将元素对调
        float t = myList[i];
        myList[i] = myList[j];
        myList[j] = t;
        ++i;
        --j;
    }
}



//构造结点
listNode::listNode(float nodeData, listNode* succ)
    : data(nodeData), next(succ) {}

listNode::~listNode() {} 


//链表的初始化
linkList::linkList(const int& initLen, float initArr[]) {
    firstNode = new listNode();//firstNode是头结点而不是首元结点
    lastNode  = nullptr;//初始时将表尾结点置空
    listSize = 0;//初始时将链表长度初始化为0
    for (int i = 0; i < initLen; ++i)
        tailInsertItem(initArr[i]);   //利用已有尾插接口进行初始化
}

//销毁链表
linkList::~linkList()
{
    curNode=firstNode;
    while(curNode)
    {
        listNode *cur=curNode;
        curNode=curNode->next;
        delete cur;//将结点逐个释放
    }
}

//插入元素（头插法）
bool linkList::headInsertItem(const float& num)
{
    listNode *s=new listNode(num);
    s->next=firstNode->next;
    firstNode->next=s;//将需要插入的结点s直接插入到头结点firstNode之后
    if(listSize==0) lastNode=s;//特殊情况更新lastNode结点
    listSize++;//更新链表长度
    return true;
}

//插入元素（尾插法）
bool linkList::tailInsertItem(const float& num)
{
    listNode *s=new listNode(num);
    if (lastNode == nullptr) {       //讨论为空表的情况，避免lastNode->next越界访问  
        firstNode->next = s;
        lastNode = s;
    }
    else
    {
        lastNode->next=s;
        lastNode=s;//尾插
    }
    listSize++;//更新链表长度
    return true;
}

//插入特定位置
int linkList::insertItem(const int& index,const float& num)
{
    if(index<0||index>=listSize) return -1;
    listNode *s=new listNode(num);
    curNode=firstNode;//不能用new来构造，因为firstNode已经存在，已经占用了空间
    for(int i=0;i<index;i++)
    {
        curNode=curNode->next;
    }//找到需要插入的位置的前一个结点
    s->next=curNode->next;
    curNode->next=s;
    if(s->next==NULL) lastNode=s;//更新lastNode
    listSize++;//更新链表长度
    return index;
}

//删除元素
int linkList::deleteItem(const float& num)
{
    curNode=firstNode->next;//将curNode初始设为首元结点
    int index=0;//位置计数器
    while(curNode->next)
    {
        if(curNode->next->data==num)
        {
            listNode *cur=curNode->next;//创建一个临时结点，方便后面释放
            curNode->next=curNode->next->next;
            delete cur;//释放临时结点
            listSize--;//更新链表长度
            return index+1;//返回删除的元素的位置
        }
        else
        {
            curNode=curNode->next;//结点后移
            index++;//更新位置
        }
    }
    return -1;//没找到就返回-1
}

//查找元素（按序号找）
bool linkList::locate(const int& index, float& val)
{
    if(index<0||index>listSize) return false;//不合理的index
    curNode=firstNode->next;//将curNode指向首元结点
    for(int i=0;i<index;i++)
    {
        curNode=curNode->next;
    }
    val=curNode->data;//将找到的元素的值赋值给val
    return true;
} 

//查找元素（按值查找）
int linkList::locate(const float& num)
{
    curNode=firstNode->next;
    int index=0;
    while(curNode)
    {
        if(curNode->data==num) return index;//找到了就返回位置
        else
        {
            curNode=curNode->next;
            index++;
        }
    }
    return -1;//没找到返回-1
}

//递增排序
void linkList::ascendingOrder()
{
    if (listSize < 2) return;

    listNode* newHead = nullptr;          // 已排链头（真数据）
    listNode* curr    = firstNode->next;  // 待拆链头（真数据）

    while (curr)
    {
        listNode* nxt = curr->next;       // 保存后继

        /* 把 curr 插入 newHead 的合适位置 */
        if (!newHead || curr->data < newHead->data)
        {
            curr->next = newHead;
            newHead    = curr;
        }
        else
        {
            listNode* pre = newHead;
            while (pre->next && pre->next->data <= curr->data)
                pre = pre->next;

            curr->next = pre->next;
            pre->next  = curr;
        }
        curr = nxt;
    }

    /* 把头结点接回已排链 */
    firstNode->next = newHead;
    /* 更新 lastNode */
    lastNode = newHead;
    while (lastNode && lastNode->next) lastNode = lastNode->next;
}

//逆排
void linkList::reverse()
{
    //即反转链表
    if (listSize < 2) return;// 0 或 1 个真节点无需反转
    listNode *prev = nullptr;         
    listNode *curr = firstNode->next;  
    lastNode = curr;// 反转后它会变成尾
    while (curr) {
        listNode *nxt = curr->next;    
        curr->next = prev;             
        prev = curr;                   
        curr = nxt;                    
    }
    firstNode->next = prev;//更新首元结点
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        curNode = curNode->next;
    }
}

//merge算法的实现
void merge(linkList& a, linkList& b)
{
    a.reverse();
    b.reverse();//先将已经升序排列的两个链表通过reverse降序排列
    listNode *p=a.firstNode->next;
    listNode *q=b.firstNode->next;
    listNode *cur=a.firstNode;
    a.listSize=0;
    while(p&&q)
    {
        if(p->data<q->data)
        {
            cur->next=q;
            q=q->next;
            a.listSize++;
        }
        else
        {
            cur->next=p;
            p=p->next;
            a.listSize++;
        }
        cur=cur->next;
    }//退出循环时p和q必有一个为空
    if (p) //若p不为空，则p后面的所有结点均要加到此时的链表a后
    {
    cur->next = p;
    while (p) {
        a.listSize++;
        cur = p;
        p = p->next;
    }
    } 
    else if (q) 
    {
    cur->next = q;
    while (q) {
        a.listSize++;
        cur = q;
        q = q->next;
    }
    }
    a.lastNode = cur;//更新链表a的lastNode结点
    a.lastNode->next = nullptr;  //将链表a最后一个结点的next域置空
    b.firstNode->next=nullptr;
    b.lastNode=nullptr;
    b.listSize=0; //将b清空
}